#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    //二叉树中和为目标值的路径
    void pathTargetR(TreeNode *root, int target, vector<vector<int>> &vv, vector<int> &list)
    {
        if (root == nullptr)
            return; // 结束条件

        // 将当前节点加到list
        list.push_back(root->val);
        target -= root->val;

        // 判断targer是否为0，且当前节点为整个路径的最后一个节点
        if (target == 0 && root->left == nullptr && root->right == nullptr)
            vv.push_back(list); // 推送到总路径和中

        // 递归左子树，右子树
        pathTargetR(root->left, target, vv, list);
        pathTargetR(root->right, target, vv, list);

        // 回溯处理：list删除当前节点
        // targer回到处理当前节点的状态
        list.pop_back();
    }

    vector<vector<int>> pathTarget(TreeNode *root, int target)
    {
        vector<vector<int>> vv;
        vector<int> list;
        // 处理函数
        pathTargetR(root, target, vv, list);

        return vv;
    }

    //判断搜索二叉树的后续遍历序列
    bool verifyTreeOrderR(vector<int>& post, int begin, int end)
    {
        //递归结束的条件:一个节点、nullptr
        if(begin >= end) return true;

        //判断后续遍历的内容:
        int i = begin;
        //找到右子树下标,end下标位置为根节点无需再判断
        while(post[i] < post[end]) i++;

        int j = i;//j为右子树的下标
        //判断右子树的是否都大于根节点
        while(post[j] > post[end]) j++;

        //j == end表示右子树序列没问题
        return j == end && verifyTreeOrderR(post, begin, i - 1) 
        && verifyTreeOrderR(post, i, end - 1);

    }
    bool verifyTreeOrder(vector<int>& postorder) 
    {
        int n = postorder.size();

        return verifyTreeOrderR(postorder, 0, n - 1);
    }
};

int main()
{
    return 0;
}